package com.atguigu.structures.tree.huffman;

import com.atguigu.structures.tree.node.HuffmanNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 赫夫曼树
 *
 * @author xr-8
 * @date 2022-12-04
 * @time 23:15
 */
public class HuffmanTree {

    /**
     * 创建赫夫曼树的方法
     *
     * @param arr 需要创建成哈夫曼树的数组
     * @return 创建好后的赫夫曼树的root结点
     */
    public static HuffmanNode createHuffmanTree(int[] arr) {
        // arr数组转对象list
        List<HuffmanNode> HuffmanNodes = new ArrayList<>();
        for (int value : arr) {
            HuffmanNodes.add(new HuffmanNode(value));
        }

        while(HuffmanNodes.size() > 1) {
            //排序 从小到大
            Collections.sort(HuffmanNodes);
            System.out.println("HuffmanNodes =" + HuffmanNodes);

            //取出根节点权值最小的两颗二叉树
            //(1) 取出权值最小的结点（二叉树）
            HuffmanNode leftHuffmanNode = HuffmanNodes.get(0);
            //(2) 取出权值第二小的结点（二叉树）
            HuffmanNode rightHuffmanNode = HuffmanNodes.get(1);

            //(3)构建一颗新的二叉树
            HuffmanNode parent = new HuffmanNode(leftHuffmanNode.weight + rightHuffmanNode.weight);
            parent.left = leftHuffmanNode;
            parent.right = rightHuffmanNode;

            //(4)从ArrayList删除处理过的二叉树
            HuffmanNodes.remove(leftHuffmanNode);
            HuffmanNodes.remove(rightHuffmanNode);
            //(5)将parent加入到HuffmanNodes
            HuffmanNodes.add(parent);
        }
        //返回哈夫曼树的root结点
        return HuffmanNodes.get(0);
    }

    //编写一个前序遍历的方法
    public static void preOrder(HuffmanNode root) {
        if(root != null) {
            root.preOrder();
        }else{
            System.out.println("是空树，不能遍历~~");
        }
    }

}
